package com.leetcode.algorithm.y22.m06;

/**
 * 53. 最大子数组和
 * 
 * https://leetcode.cn/problems/maximum-subarray/
 * 
 * @author jie.deng
 *
 */
class Question0053Solution01 {

	public int maxSubArray(int[] nums) {
		int len = nums.length;

		// DP状态定义
		// dp[i]表示以nums[i]结尾的连续子数组的最大和
		int[] dp = new int[len];

		// DP状态初始化
		dp[0] = nums[0];

		for (int i = 1; i < len; i++) {
			// DP状态转移方程
			dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
		}

		// 求结果集
		int maxSum = dp[0];
		for (int i = 1; i < len; i++) {
			if (dp[i] > maxSum) {
				maxSum = dp[i];
			}
		}
		return maxSum;
	}

}